package JavaStudy.sort;

/**
 * Created by hgx on 2017/3/6.
 * 快速排序
 */

public class QuickSort {
    public static int[] quickSort(int[] a, int low, int high) {
        if (low < high) {
            int middle = getMiddle(a, low, high);
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
        return a;
    }

    public static int getMiddle(int[] a, int low, int high) {
        int temp = a[low];
        while (low < high) {
            //从右向左找比基准小的元素并交换
            while (low < high && a[high] >= temp) {
                high--;
            }
            a[low] = a[high];
            //从左往右找比基准大的元素并交换
            while (low < high && a[low] <= temp) {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;

        for (int kkk:a){
            System.out.print(kkk);
        }
        System.out.println("  ");

        return low;
    }

    public static void main(String[] args) {
        int[] a={4,6,3,9,5,7,1,8,2};
        for (int kkk:a){
            System.out.print(kkk);
        }
        System.out.println("  开始");
        int[] b=quickSort(a,0,8);
    }
}
